// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现类型参数替换。

package types

import "go/token"

type substMap map[*TypeParam]Type

// makeSubstMap创建一个新的替换映射，将tpars[i]映射到targs[i]。
// 如果targs[i]为零，则不替换tpars[i]。
func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
	assert(len(tpars) == len(targs))
	proj := make(substMap, len(tpars))
	for i, tpar := range tpars {
		proj[tpar] = targs[i]
	}
	return proj
}

// makeRenameMap类似于MakeSubsMap，但创建了一个映射，用于重命名from中的类型
// parameters和to中的类型参数。
func makeRenameMap(from, to []*TypeParam) substMap {
	assert(len(from) == len(to))
	proj := make(substMap, len(from))
	for i, tpar := range from {
		proj[tpar] = to[i]
	}
	return proj
}

func (m substMap) empty() bool {
	return len(m) == 0
}

func (m substMap) lookup(tpar *TypeParam) Type {
	if t := m[tpar]; t != nil {
		return t
	}
	return tpar
}

// subst递归返回类型typ，其类型参数tpars替换为
// 相应的类型参数targs。subst的纯粹含义是
// 它不修改传入类型。如果发生替换，则
// 结果类型与传入类型不同。
// 
// 如果给定的上下文为非零，则使用它代替检查。配置。上下文
func (check *Checker) subst(pos token.Pos, typ Type, smap substMap, ctxt *Context) Type {
	if smap.empty() {
		return typ
	}

	// 常见情况
	switch t := typ.(type) {
	case *Basic:
		return typ // 无需执行
	case *TypeParam:
		return smap.lookup(t)
	}

	// 一般情况
	subst := subster{
		pos:   pos,
		smap:  smap,
		check: check,
		ctxt:  check.bestContext(ctxt),
	}
	return subst.typ(typ)
}

type subster struct {
	pos   token.Pos
	smap  substMap
	check *Checker // 如果通过实例化
	ctxt  *Context
}

func (subst *subster) typ(typ Type) Type {
	switch t := typ.(type) {
	case nil:
		// 调用typernil，如果typ可能为nil。
		panic("nil typ")

	case *Basic:
		// 无需执行

	case *Array:
		elem := subst.typOrNil(t.elem)
		if elem != t.elem {
			return &Array{len: t.len, elem: elem}
		}

	case *Slice:
		elem := subst.typOrNil(t.elem)
		if elem != t.elem {
			return &Slice{elem: elem}
		}

	case *Struct:
		if fields, copied := subst.varList(t.fields); copied {
			s := &Struct{fields: fields, tags: t.tags}
			s.markComplete()
			return s
		}

	case *Pointer:
		base := subst.typ(t.base)
		if base != t.base {
			return &Pointer{base: base}
		}

	case *Tuple:
		return subst.tuple(t)

	case *Signature:
		// 保留接收器：在*接口和*命名类型
		// 替换期间处理。
		// 
		// 在这里简单地进行替换可能会导致
		// 在接收器是接口的情况下出现无限递归。例如，考虑
		// 循环，所以在recv中替换会导致
		// recv->interface->recv->interface->。。。
		recv := t.recv

		params := subst.tuple(t.params)
		results := subst.tuple(t.results)
		if params != t.params || results != t.results {
			return &Signature{
				rparams: t.rparams,
				// TODO（rFindley）为什么我们不能在这里取消Tparam，而不是在实例化中？
				tparams: t.tparams,
				// 实例化签名的作用域为零
				recv:     recv,
				params:   params,
				results:  results,
				variadic: t.variadic,
			}
		}

	case *Union:
		terms, copied := subst.termlist(t.terms)
		if copied {
			// 术语列表替换可能会引入重复的术语（不太可能，但可能）。
			// 这没关系；惰性类型集计算将以正常形式确定实际类型集
			// 。
			return &Union{terms}
		}

	case *Interface:
		methods, mcopied := subst.funcList(t.methods)
		embeddeds, ecopied := subst.typeList(t.embeddeds)
		if mcopied || ecopied {
			iface := subst.check.newInterface()
			iface.embeddeds = embeddeds
			iface.implicit = t.implicit
			iface.complete = t.complete
			// 如果我们更改了接口类型，如果接收器类型是原始接口，我们可能需要更换其
			// 接收器。
			// /*命名类型的接收器在命名类型扩展期间被替换。
			// 
			// 值得注意的是，即使接收器类型可以参数化，也可以访问此处而不创建新的*接口。例如：
			// 
			// type T[P any]interface{m（）}
			// 
			// 在这种情况下，将不在此处替换接口，因为其
			// 方法签名不依赖于类型参数P，但是我们仍然需要创建新的接口方法来保存实例化的
			// 接收器。这是由ExpandName处理的。
			iface.methods, _ = replaceRecvType(methods, t, iface)
			return iface
		}

	case *Map:
		key := subst.typ(t.key)
		elem := subst.typ(t.elem)
		if key != t.key || elem != t.elem {
			return &Map{key: key, elem: elem}
		}

	case *Chan:
		elem := subst.typ(t.elem)
		if elem != t.elem {
			return &Chan{dir: t.dir, elem: elem}
		}

	case *Named:
		// dump用于调试
		dump := func(string, ...any) {}
		if subst.check != nil && trace {
			subst.check.indent++
			defer func() {
				subst.check.indent--
			}()
			dump = func(format string, args ...any) {
				subst.check.trace(subst.pos, format, args...)
			}
		}

		// subst由ExpandName调用，所以在这个函数中我们需要是
		// 小心不要调用任何会导致t被扩展的方法：执行
		// 这样会导致死锁。
		// 
		// 所以我们叫t.orig。这里是TypeParams（），而不是t.TypeParams（），下面是
		// 。
		if t.orig.TypeParams().Len() == 0 {
			dump(">>> %s is not parameterized", t)
			return t // 类型未参数化
		}

		var newTArgs []Type
		if t.targs.Len() != t.orig.TypeParams().Len() {
			return Typ[Invalid] // 其他地方报告的错误
		}

		// 已实例化
		dump(">>> %s already instantiated", t)
		// 对于每个（现有）类型参数targ，确定是否需要替换
		// ；i、 例如，如果它是或包含一个类型参数
		// ，则它有一个类型参数。
		for i, targ := range t.targs.list() {
			dump(">>> %d targ = %s", i, targ)
			new_targ := subst.typ(targ)
			if new_targ != targ {
				dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
				if newTArgs == nil {
					newTArgs = make([]Type, t.orig.TypeParams().Len())
					copy(newTArgs, t.targs.list())
				}
				newTArgs[i] = new_targ
			}
		}

		if newTArgs == nil {
			dump(">>> nothing to substitute in %s", t)
			return t // 无需替换
		}

		// 在创建新的命名类型之前，请检查此类型是否已存在
		h := subst.ctxt.instanceHash(t.orig, newTArgs)
		dump(">>> new type hash: %s", h)
		if named := subst.ctxt.lookup(h, t.orig, newTArgs); named != nil {
			dump(">>> found %s", named)
			return named
		}

		// 创建一个新实例并填充上下文，以避免无休止的
		// 递归。此处使用的位置无关紧要，因为t上只发生了验证
		// （我们不在named上调用validType），但我们使用subst.pos来帮助调试。注意，如果我们要更普遍地公开替换（不仅仅是在声明的上下文中），我们必须在
		t.orig.resolve(subst.ctxt)
		return subst.check.instance(subst.pos, t.orig, newTArgs, subst.ctxt)

		// 中替换。还有潜在的。
		// 
		// 但现在这是不必要的。

	case *TypeParam:
		return subst.smap.lookup(t)

	default:
		panic("unimplemented")
	}

	return typ
}

// typernil类似于typ，但如果参数为nil，则替换为typ[Invalid]。
func (subst *subster) typOrNil(typ Type) Type {
	if typ == nil {
		return Typ[Invalid]
	}
	return subst.typ(typ)
}

func (subst *subster) var_(v *Var) *Var {
	if v != nil {
		if typ := subst.typ(v.typ); typ != v.typ {
			return substVar(v, typ)
		}
	}
	return v
}

func substVar(v *Var, typ Type) *Var {
	copy := *v
	copy.typ = typ
	return &copy
}

func (subst *subster) tuple(t *Tuple) *Tuple {
	if t != nil {
		if vars, copied := subst.varList(t.vars); copied {
			return &Tuple{vars: vars}
		}
	}
	return t
}

func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
	out = in
	for i, v := range in {
		if w := subst.var_(v); w != v {
			if !copied {
				new := make([]*Var, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = w
		}
	}
	return
}

func (subst *subster) func_(f *Func) *Func {
	if f != nil {
		if typ := subst.typ(f.typ); typ != f.typ {
			copy := *f
			copy.typ = typ
			return &copy
		}
	}
	return f
}

func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
	out = in
	for i, f := range in {
		if g := subst.func_(f); g != f {
			if !copied {
				new := make([]*Func, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = g
		}
	}
	return
}

func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
	out = in
	for i, t := range in {
		if u := subst.typ(t); u != t {
			if !copied {
				new := make([]Type, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = u
		}
	}
	return
}

func (subst *subster) termlist(in []*Term) (out []*Term, copied bool) {
	out = in
	for i, t := range in {
		if u := subst.typ(t.typ); u != t.typ {
			if !copied {
				new := make([]*Term, len(in))
				copy(new, out)
				out = new
				copied = true
			}
			out[i] = NewTerm(t.tilde, u)
		}
	}
	return
}

func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
	out = in
	for i, method := range in {
		sig := method.Type().(*Signature)
		if sig.recv != nil && sig.recv.Type() == old {
			if !copied {
				out = make([]*Func, len(in))
				copy(out, in)
				copied = true
			}
			newsig := *sig
			newsig.recv = substVar(sig.recv, new)
			out[i] = NewFunc(method.pos, method.pkg, method.name, &newsig)
		}
	}
	return
}
